// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class CompletenessOfBinaryTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }


    public TreeNode[] queue = new TreeNode[101];
    public int l,r;
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        l = 0; r = 0;

        queue[r++] = root;
        boolean flg = false;

        while (l < r){
            TreeNode node = queue[l++];
            if( (node.left == null && node.right != null )  //左节点为空，右节点不为空则不是完全二叉树
            ||( flg && (node.left != null || node.right != null ) ) //之前已经有空节点了，但现在又出现不是空结点则不是完全二叉树
            ){
                return false;
            }
            if(node.left != null){
                queue[r++] = node.left;
            }
            if(node.right != null){
                queue[r++] = node.right;
            }
            if(node.left == null || node.right == null){
                flg = true;
            }
        }
        return true;
    }
}
